/*
 * @Author: szx
 * @Date: 2021-11-26 13:09:52
 * @LastEditTime: 2021-12-29 13:37:23
 * @Description:
 * @FilePath: \leetcode\1-99\46\46.js
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// var permute = function (nums) {
//     const n = nums.length;
//     const res = [];
//     const dfs = function (num, index) {
//         if (index == n) {
//             res.push(num);
//         }
//         for (let i = index; i < n; i++) {
//             let tmp = num[i];
//             num[i] = num[index];
//             num[index] = tmp;
//             dfs(num.slice(), index + 1);
//             num[index] = num[i];
//             num[i] = tmp;
//         }
//     };
//     dfs(nums.slice(), 0);
//     return res;
// };

// 填数字，如果填过了，那么就跳过，如果没填过，就往里面填写
// var permute = function (nums) {
//     let res = [],
//         path = [],
//         used = [];

//     const dfs = () => {
//         if (path.length == nums.length) {
//             res.push(Array.from(path));
//             return;
//         }
//         for (let i = 0; i < nums.length; i++) {
//             // 填过了
//             if (used[i]) continue;
//             // 没填过，填一下
//             path.push(nums[i]);
//             used[i] = true;
//             dfs();
//             // 填完了记得变回去
//             path.pop();
//             used[i] = false;
//         }
//     };
//     dfs();
//     return res;
// };

// var permute = function (nums) {
//     const res = [];
//     const len = nums.length;
//     const backtrace = (nums, index) => {
//         if (index == len) {
//             res.push(nums);
//             return;
//         }
//         for (let i = index; i < len; i++) {
//             [nums[i], nums[index]] = [nums[index], nums[i]];
//             backtrace(nums.slice(), index + 1);
//             [nums[i], nums[index]] = [nums[index], nums[i]];
//         }
//     };
//     backtrace(nums.slice(), 0);
//     return res;
// };

var permute = function (nums) {
    const len = nums.length;
    const res = [];
    const path = [];
    const used = new Array(len).fill(false);
    const backtrace = () => {
        if (path.length == len) {
            res.push(path.slice());
            return;
        }
        for (let i = 0; i < len; i++) {
            if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true;
            backtrace();
            used[i] = false;
            path.pop();
        }
    };
    backtrace();
    return res;
};
console.log(permute([1, 2, 3]));
